/*
形成一个整数对x; y 
保证如果甲到2号监狱那么一共要有x个囚犯从1号监狱到2号监狱
而y个囚犯从2号监狱必须得到1号监狱
分割二部图为一些整数对后
我们希望选择一部分整数对使它们的和为Sum(x) = Sum(y)
并且是小于n=2的最大数。这部分就可以用背包动规来完成

*/
#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int const MAXM = 202;  // the max value of m
int num_case , m , r ;  // just as the problem describes
int groupNum;           // 组号
bool visited[2*MAXM];   // 是否已经被访问过
bool G[MAXM][MAXM];     // Gragh
int Left[2*MAXM] , Right[2*MAXM];   // 每个连通子集左边的人数和右边的人数
bool dp[MAXM/2][MAXM/2];        // DP[i][j]=true表示左边i个人与右边j个人交换能够成功，否则不行
 
// DFS:搜索连通分量 ，注意，孤立点作为一个特殊的连通分量
void dfs(int a)
{
    // termination condition
    if( true == visited[a] )
        return;
    visited[a] = true;
    if( a <= m )    // 左边的人
        Left[ groupNum ] ++;
    else            // 右边的人
        Right[ groupNum ] ++;
    // search for its neighbors
    if( a <= m )    // 这个人在左边
    {
        for(int i=m+1;i<=2*m;i++)
            if( true == G[a][i-m] && false == visited[i] )
                dfs( i );
    }
    else        // 这个人在右边
    {
        for(int i=1;i<=m;i++)
        {
            if( true == G[i][a-m] && false == visited[i] )
                dfs( i );
        }
    }
}
 
int main()
{
    scanf("%d",&num_case);
 
    while( num_case -- )
    {
        int i , j , k;
        // Initialization
        memset( G , 0 , sizeof(G) );
        memset( visited , 0 , sizeof(visited) );
        memset( Left , 0 , sizeof(Left) );
        memset( Right , 0 , sizeof(Right) );
        memset( dp , 0 , sizeof(dp) );
//        memset( Left_visited , 0 , sizeof(Left_visited) );
        groupNum = 1;// 组号，从1开始计数
        // input
        scanf("%d%d",&m , &r );
        int t1 , t2 ;
        for(i=0;i<r;i++)
        {
            scanf("%d%d",&t1 , &t2 );
            G[t1][t2] = true;
        }
        // process: 遍历所有的人
        for(i=1;i<=2*m;i++)
            if(  false == visited[i] )  // 没有被访问
             {
                dfs(i);
                groupNum ++;
             }
        // 开始DP
        groupNum --;    // 此时的groupNum就是连通子集的数目
        // 如何理解这个DP？我们考察dp[i][j]能否达到，并考察第k个连通分量的人是否要交换
        // 如果不交换第i个连通分量，那么dp[i][j] = dp[i][j]
        // 如果交换，那么 dp[i][j] = dp[ i-Left[k] ][ j-Right[k] ]
        dp[0][0] = true;    // 初始化DP
        for(k=1;k<=groupNum;k++)
            for(i=m/2;i>=Left[k];i--)
                for(j=m/2;j>=Right[k];j--)
                {
                    if( true == dp[ i - Left[k] ][ j - Right[k] ] )
                        dp[i][j] = true;
                }
        int result = m/2 ;
        while( false == dp[result][result] )    // dp[i][i] = true ， 找到最大的i
            result --;
        printf("%d\n",result);
    }
 
    return 0;
}